package com.shm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 102. 二叉树的层序遍历
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 *
 *
 *
 * 示例：
 * 二叉树：[3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其层序遍历结果：
 *
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 * @author SHM
 */
public class LevelOrder {
    /**
     * 思路分析：
     *
     * 题目要求我们一层一层输出树的结点的值，很明显需要使用「广度优先遍历」实现；
     *
     * 广度优先遍历借助「队列」实现；
     *
     * 注意：
     *
     * 这样写 for (int i = 0; i < queue.size(); i++) { 代码是不能通过测评的，这是因为 queue.size() 在循环中是变量（这条规则在 Python 中不成立，请各位读者自行验证）。正确的做法是：每一次在队列中取出元素的个数须要先暂存起来，请见参考代码；
     * 子结点入队的时候，非空的判断很重要：在队列的队首元素出队的时候，一定要在左（右）子结点非空的时候才将左（右）子结点入队。
     * 树的广度优先遍历的写法模式相对固定：
     *
     * 使用队列；
     * 在队列非空的时候，动态取出队首元素；
     * 取出队首元素的时候，把队首元素相邻的结点（非空）加入队列。
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，这里 NN 是二叉树结点的个数，每个结点都访问一次，因此时间复杂度是 O(N)O(N)；
     * 空间复杂度：O(N)O(N)。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/bfs/e6e5f7/
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            // 注意 1：一定要先把当前队列的结点总数暂存起来
            int n = queue.size();
            List<Integer> tmp = new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode node =  queue.poll();
                tmp.add(node.val);
                // 注意 2：左（右）孩子结点非空才加入队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            ans.add(tmp);
        }
        return ans;
    }
}
